package com.maltys.greedy;

/**
 * @author malty
 * @link <a href="https://leetcode.cn/problems/maximum-subarray">最大子数组和</a>
 */
public class MaxSubarray {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = Integer.MIN_VALUE;
        int maxSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (sum + nums[i] >= 0) {
                sum += nums[i];
                maxSum = Math.max(maxSum, sum);
                max = Math.max(max, nums[i]);
            } else {
                sum = 0;
            }
        }
        return maxSum == 0 ? max : maxSum;
    }

    public static void main(String[] args) {
        MaxSubarray subarray = new MaxSubarray();
        int array = subarray.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
        System.out.println(array);
    }
}
